Odd Crossing Number Is Not Crossing Number
Identifieur interne : 001035 ( Main/Exploration ); précédent : 001034; suivant : 001036Odd Crossing Number Is Not Crossing Number
Auteurs : J. Pelsmajer [États-Unis] ; Marcus Schaefer [États-Unis] ; Daniel Štefankovi [États-Unis, Slovaquie]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2006.
Abstract
Abstract: The crossing number of a graph is the minimum number of edge intersections in a plane drawing of a graph, where each intersection is counted separately. If instead we count the number of pairs of edges that intersect an odd number of times, we obtain the odd crossing number. We show that there is a graph for which these two concepts differ, answering a well-known open question on crossing numbers. To derive the result we study drawings of maps (graphs with rotation systems).
Url:
DOI: 10.1007/11618058_35
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 000196
- to stream Istex, to step Curation: 000193
- to stream Istex, to step Checkpoint: 000A08
- to stream Main, to step Merge: 001052
- to stream Main, to step Curation: 001035
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Odd Crossing Number Is Not Crossing Number</title><author><name sortKey="Pelsmajer, J" sort="Pelsmajer, J" uniqKey="Pelsmajer J" first="J." last="Pelsmajer">J. Pelsmajer</name></author><author><name sortKey="Schaefer, Marcus" sort="Schaefer, Marcus" uniqKey="Schaefer M" first="Marcus" last="Schaefer">Marcus Schaefer</name></author><author><name sortKey="Stefankovi, Daniel" sort="Stefankovi, Daniel" uniqKey="Stefankovi D" first="Daniel" last="Štefankovi">Daniel Štefankovi</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:CF687E835155A5D8114498E92C5008CF9798AF7C</idno><date when="2006" year="2006">2006</date><idno type="doi">10.1007/11618058_35</idno><idno type="url">https://api.istex.fr/document/CF687E835155A5D8114498E92C5008CF9798AF7C/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">000196</idno><idno type="wicri:Area/Istex/Curation">000193</idno><idno type="wicri:Area/Istex/Checkpoint">000A08</idno><idno type="wicri:doubleKey">0302-9743:2006:Pelsmajer J:odd:crossing:number</idno><idno type="wicri:Area/Main/Merge">001052</idno><idno type="wicri:Area/Main/Curation">001035</idno><idno type="wicri:Area/Main/Exploration">001035</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Odd Crossing Number Is Not Crossing Number</title><author><name sortKey="Pelsmajer, J" sort="Pelsmajer, J" uniqKey="Pelsmajer J" first="J." last="Pelsmajer">J. Pelsmajer</name><affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country><placeName><region type="state">Illinois</region></placeName><wicri:cityArea>Department of Applied Mathematics, Illinois Institute of Technology, 60616, Chicago</wicri:cityArea></affiliation><affiliation wicri:level="1"><country wicri:rule="url">États-Unis</country></affiliation></author><author><name sortKey="Schaefer, Marcus" sort="Schaefer, Marcus" uniqKey="Schaefer M" first="Marcus" last="Schaefer">Marcus Schaefer</name><affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country><placeName><region type="state">Illinois</region></placeName><wicri:cityArea>Department of Computer Science, DePaul University, 60604, Chicago</wicri:cityArea></affiliation><affiliation wicri:level="1"><country wicri:rule="url">États-Unis</country></affiliation></author><author><name sortKey="Stefankovi, Daniel" sort="Stefankovi, Daniel" uniqKey="Stefankovi D" first="Daniel" last="Štefankovi">Daniel Štefankovi</name><affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country><placeName><region type="state">État de New York</region></placeName><wicri:cityArea>Department of Computer Science, University of Rochester, 14627, Rochester</wicri:cityArea></affiliation><affiliation wicri:level="1"><country xml:lang="fr">Slovaquie</country><wicri:regionArea>Department of Computer Science, Comenius University, Bratislava</wicri:regionArea><wicri:noRegion>Bratislava</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">États-Unis</country></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2006</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">CF687E835155A5D8114498E92C5008CF9798AF7C</idno><idno type="DOI">10.1007/11618058_35</idno><idno type="ChapterID">35</idno><idno type="ChapterID">Chap35</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: The crossing number of a graph is the minimum number of edge intersections in a plane drawing of a graph, where each intersection is counted separately. If instead we count the number of pairs of edges that intersect an odd number of times, we obtain the odd crossing number. We show that there is a graph for which these two concepts differ, answering a well-known open question on crossing numbers. To derive the result we study drawings of maps (graphs with rotation systems).</div></front></TEI><affiliations><list><country><li>Slovaquie</li><li>États-Unis</li></country><region><li>Illinois</li><li>État de New York</li></region></list><tree><country name="États-Unis"><region name="Illinois"><name sortKey="Pelsmajer, J" sort="Pelsmajer, J" uniqKey="Pelsmajer J" first="J." last="Pelsmajer">J. Pelsmajer</name></region><name sortKey="Pelsmajer, J" sort="Pelsmajer, J" uniqKey="Pelsmajer J" first="J." last="Pelsmajer">J. Pelsmajer</name><name sortKey="Schaefer, Marcus" sort="Schaefer, Marcus" uniqKey="Schaefer M" first="Marcus" last="Schaefer">Marcus Schaefer</name><name sortKey="Schaefer, Marcus" sort="Schaefer, Marcus" uniqKey="Schaefer M" first="Marcus" last="Schaefer">Marcus Schaefer</name><name sortKey="Stefankovi, Daniel" sort="Stefankovi, Daniel" uniqKey="Stefankovi D" first="Daniel" last="Štefankovi">Daniel Štefankovi</name><name sortKey="Stefankovi, Daniel" sort="Stefankovi, Daniel" uniqKey="Stefankovi D" first="Daniel" last="Štefankovi">Daniel Štefankovi</name></country><country name="Slovaquie"><noRegion><name sortKey="Stefankovi, Daniel" sort="Stefankovi, Daniel" uniqKey="Stefankovi D" first="Daniel" last="Štefankovi">Daniel Štefankovi</name></noRegion></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/OcrV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001035 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 001035 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Ticri/CIDE
|area= OcrV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:CF687E835155A5D8114498E92C5008CF9798AF7C
|texte= Odd Crossing Number Is Not Crossing Number
}}
| This area was generated with Dilib version V0.6.32. |  |